ICPC，大学生ACM竞赛经典模板备战ACM
1、 几何.........................................................................................................................191.1 注意.................................................................................................................191.2 几何公式.........................................................................................................191.3 多边形.............................................................................................................211.4 多边形切割.....................................................................................................241.5 浮点函数.........................................................................................................251.6 面积.................................................................................................................301.7 球面.................................................................................................................311.8 三角形.............................................................................................................321.9 三维几何.........................................................................................................341.10 凸包.................................................................................................................411.11 网格.................................................................................................................431.12 圆.....................................................................................................................431.13 整数函数.........................................................................................................452、 组合.........................................................................................................................482.1 组合公式..................................................................................................................482.2 排列组合生成..........................................................................................................482.3 生成 gray 码.............................................................................................................502.4 置换(polya)..............................................................................................................502.5 字典序全排列..........................................................................................................512.6 字典序组合513 、结 构.........................................................................................................................................523.1 并查集......................................................................................................................523.2 堆..............................................................................................................................533.3 线段树......................................................................................................................543.4 子段和......................................................................................................................593.5 子阵和594 、数 论.........................................................................................................................................604.1 阶乘最后非 0 位......................................................................................................604.2 模线性方程组..........................................................................................................614.3 素数..........................................................................................................................624.4 欧拉函数635 、数值计算.........................................................................................................................................645.1 定积分计算(Romberg) ............................................................................................645.2 多项式求根(牛顿法)...............................................................................................665.3 周期性方程(追赶法)676 、图 论 — NP 搜 索.........................................................................................................................................686.1 最大团......................................................................................................................686.2 最大团(n<64)(faster)697 、图 论 — 连通性.........................................................................................................................................717.1 无向图关键点(dfs 邻接阵) .....................................................................................717.2 无向图关键边(dfs 邻接阵) .....................................................................................727.3 无向图的块(bfs 邻接阵) .........................................................................................737.4 无向图连通分支(dfs/bfs 邻接阵) ...........................................................................747.5 有向图强连通分支(dfs/bfs 邻接阵) .......................................................................757.6 有向图最小点基(邻接阵)768 、图 论 — 匹 配.........................................................................................................................................778.1 二分图最大匹配(hungary 邻接表).........................................................................778.2 二分图最大匹配(hungary 邻接阵).........................................................................788.3 二分图最大匹配(hungary 正向表).........................................................................788.4 二分图最佳匹配(kuhn_munkras 邻接阵) ...............................................................798.5 一般图匹配(邻接表)...............................................................................................8048.6 一般图匹配(邻接阵)...............................................................................................818.7 一般图匹配(正向表)819 、图 论 — 网络流.........................................................................................................................................829.1 最大流(邻接阵).......................................................................................................829.2 上下界最大流(邻接阵)...........................................................................................839.3 上下界最小流(邻接阵)...........................................................................................849.4 最大流无流量(邻接阵)...........................................................................................859.5 最小费用最大流(邻接阵).......................................................................................8510、 图论—应用.............................................................................................................8610.1 欧拉回路(邻接阵).........................................................................................................8610.2 树的前序表转化............................................................................................................8710.3 树的优化算法................................................................................................................8810.4 拓扑排序(邻接阵).........................................................................................................8910.5 最佳边割集....................................................................................................................9010.6 最佳点割集....................................................................................................................9110.7 最小边割集....................................................................................................................9210.8 最小点割集....................................................................................................................9310.9 最小路径覆盖................................................................................................................95 11、 图论—支撑树.........................................................................................................9511.1 最小生成树(kruskal 邻接表).................................................................................9511.2 最小生成树(kruskal 正向表).................................................................................9711.3 最小生成树(prim binary_heap 邻接表)...............................................................9811.4 最小生成树(prim binary_heap 正向表)...............................................................9911.5 最小生成树(prim mapped_heap 邻接表) ..........................................................10011.6 最小生成树(prim mapped_heap 正向表) ..........................................................10211.7 最小生成树(prim 邻接阵)...................................................................................10311.8 最小树形图(邻接阵) ...........................................................................................1031612、 图论—最短路径...................................................................................................10512.1 最短路径(单源 bellman_ford 邻接阵)................................................................10512.2 最短路径(单源 dijkstra bfs 邻接表)..................................................................10512.3 最短路径(单源 dijkstra bfs 正向表)..................................................................10612.4 最短路径(单源 dijkstra binary_heap 邻接表) ...................................................10712.5 最短路径(单源 dijkstra binary_heap 正向表) ...................................................10812.6 最短路径(单源 dijkstra mapped_heap 邻接表).................................................10912.7 最短路径(单源 dijkstra mapped_heap 正向表).................................................11012.8 最短路径(单源 dijkstra 邻接阵)......................................................................... 11112.9 最短路径(多源 floyd_warshall 邻接阵) .............................................................1121713、 应用.......................................................................................................................11213.1 Joseph 问题...........................................................................................................11213.2 N 皇后构造解.......................................................................................................11313.3 布尔母函数..........................................................................................................11413.4 第 k 元素..............................................................................................................11413.5 幻方构造..............................................................................................................11513.6 模式匹配(kmp)....................................................................................................11613.7 逆序对数..............................................................................................................11713.8 字符串最小表示..................................................................................................11713.9 最长公共单调子序列..........................................................................................11813.10 最长子序列........................................................................................................11913.11 最大子串匹配....................................................................................................12013.12 最大子段和........................................................................................................12113.13 最大子阵和........................................................................................................12118
评论